package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname LongestPalindromicSubstring
 * @Description Leetcode 5. 最长回文子串 中等难度 动态规划
 * @Date 2021/10/1 20:34
 * @Version 1.0
 */
public class LongestPalindromicSubstring {

    /**
     * 双指针思路 中心拓展思路
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {

        int len = s.length();
        int maxLen = Integer.MIN_VALUE;
        String res = "";

        if (len == 1) {
            return s;
        }

        for (int i = 0; i < 2 * len - 1; i++) {

            int left = i / 2;
            int right = i / 2 + i % 2;

            int count = 0;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {

                if (left != right) {
                    count += 2;
                } else {
                    count++;
                }
                left--;
                right++;


            }

            if (count > maxLen) {
                maxLen = count;


                res = s.substring(left + 1, right);
            }

        }


        return res;
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring longestPalindromicSubstring = new LongestPalindromicSubstring();
        String s = longestPalindromicSubstring.longestPalindrome("babad");

        System.out.println(s);
    }
}
